package hot_100;

public class 最长回文子串 {
    public static void main(String[] args) {

    }

    public String longestPalindrome(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[n + 1][n + 1];
        int l = 0, r = 0;
        for (int i = 1; i <= n; i++) {
            for (int st = 0; st + i - 1 < n; st++) {
                int ed = st + i - 1;
                if (i == 1) {
                    dp[i][i] = true;
                    continue;
                }
                if (chars[st] == chars[ed] && (dp[st + 1][ed - 1]||st>=ed)) {
                    dp[st][ed] = true;
                    if (r - l + 1 < i) {
                        l = st;
                        r = ed;
                    }
                }
            }
        }
        return s.substring(l, r + 1);
    }

}
